package com.chenken.recursion;

/**
 *	八皇后
 *  递归回溯
 */
public class Queue {

	/**
	 * 列
	 */
	static int[] cols;
	
	/**
	 * 一共有多少种摆法
	 */
	static int ways;
	
	public static void main(String[] args) {
		placeQueens(8);
	}
	
	static void placeQueens(int n) {
		if(n < 1) return;
		cols = new int[n];
		//	从第0行开始摆
		place(0);
		System.out.println(n+"皇后，一共有"+ways + "种摆法");
	}
	
	/**
	 * 在第row行摆放皇后
	 * @param row
	 */
	public static void place(int row) {
		if(row == cols.length) {
			show();
			ways++;
			return;
		}
		for(int col = 0;col<cols.length;col++) {//	一共8列
			if(isValid(row,col)) {
				//	在第row行第col列摆放皇后
				cols[row] = col;
				//	摆放下一行，如果执行完，会回溯到上一个row
				place(row+1);
			}
		}
	}

	private static void show() {
		for(int row = 0;row<cols.length;row++) {
			for(int col = 0;col<cols.length;col++) {
				if(cols[row] == col) {
					System.out.print("1 ");
				}else {
					System.out.print("0 ");
				}
			}
			System.out.println();
		}
		System.out.println("-------------------------------------");
	}

	/**
	 * 判断第row行第col列是否可以摆放皇后
	 * @param row
	 * @param col
	 * @return
	 */
	private static boolean isValid(int row, int col) {
		// 	看之前行放置的皇后
		for(int i = 0;i < row; i++) {
			//	第col列已经有皇后
			if(cols[i] == col) return false;
			//	斜线上有皇后  坐标 (y1-y2)/(x1-x2) == 1 表示在同一斜线上 ----> (y1-y2) == (x1-x2)
			if(row - i == Math.abs(col-cols[i])) return false;
		}
		return true;
	}
	
	
}
